public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minSwapsCouples(new int[]{0,3,9,4,1,2,8,5,7,6}));
    }

    public int minSwapsCouples(int[] row) {
        /**
         * 情侣牵手
         *  -本题使用并查集需要一定的经验，否则很难想到
         *  已经规定0、1是情侣、2、3是情侣... 也就是说 下标/2 值相等的两个元素就是情侣
         *  我们只需将所有无法牵手的情侣放在一个集合，假设集合中有k对情侣无法牵手，那么至少交换k-1次（前k-1对情侣有序，最后一对肯定有序）*/
        // 1 初始化并查集
        initialize();

        // 2 循环数组
        for(int i = 0; i < row.length; i+=2) {
            int a = row[i]/2;
            int b = row[i+1]/2;
            if(a != b) {
                union(a, b);
            }
        }

        // 3 查找返回值
        int ret = 0;
        for(int e: size) {
            if(e - 1 > 0) {
                ret += e-1;
            }
        }
        return ret;
    }

    // 创建并查集
    public static int MAX_N = 30;
    public static int[] father = new int[MAX_N];
    public static int[] size = new int[MAX_N];
    public static int[] stack = new int[MAX_N];

    public static void initialize() {
        /**
         * 初始化并查集*/
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到代表元素并做扁平化*/
        // 1找到代表元素
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }

        // 2扁平化处理
        while(i > 0) {
            father[stack[--i]] = a;
        }

        // 3返回值
        return a;
    }

    public static void union(int a, int b) {
        /**
         * 合并并查集-小挂大优化*/
        // 1 找到代表元素
        int fa = find(a);
        int fb = find(b);

        // 2 小挂大
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                // -标记失效数据
                size[fb] = -1;
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                size[fa] = -1;
                father[fa] = fb;
            }
        }
    }
}
